package com.shangguigu.search;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * @author: ZhouBert
 * @date: 2019/10/14
 * @description: 插值查找 首先保证有序
 * 差值公式：mid=low+(high-low)*(key-arr[low])/(arr[high]-arr[low])
 * TODO:对于数据量较大，关键字分布比较均匀的查找表来说，比较快！
 * TODO:但是对于关键字分布不均匀的查找表，不一定比折半查找好！
 */
public class InsertValueSearch {

	/**
	 * 插值查找
	 *
	 * @param nums    已经排序的数组
	 * @param left    左索引
	 * @param right   右索引
	 * @param findVal 查找值
	 * @return
	 */
	public static int insertValueSearchByRecursive(int[] nums, int left, int right, int findVal) {
		System.out.printf("left:%d;right:%d", left, right);
		System.out.println();
		//todo:findVal<nums[0]||findVal>nums[nums.length-1] 这个条件必须存在，否则就会数组越界！
		if (left > right || findVal<nums[0]||findVal>nums[nums.length-1]) {
			return -1;
		}
		///todo:查找插值公式
		int insertIndex = left + (right - left) * (findVal - nums[left]) / (nums[right] - nums[left]);
		int val = nums[insertIndex];
		if (findVal == val) {
			return insertIndex;
		}
		if (findVal > val) {
			///如果计算的依然是本次传参，说明没有该元素，要跳出死循环
			if (insertIndex + 1 == left) {
				return -1;
			}
			///left=insertIndex+1;
			return insertValueSearchByRecursive(nums, insertIndex + 1, right, findVal);
		} else {
			if (insertIndex - 1 == right) {
				return -1;
			}
			///right=insertIndex-1;
			return insertValueSearchByRecursive(nums, left, insertIndex - 1, findVal);
		}

	}

	/**
	 * 测试插值算法的均匀分布
	 */
	@Test
	public void testEvenlyArray() {
		int[] arr = new int[100];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = i + 1;
		}
		arr[30] = 0;
		Arrays.sort(arr);
		int index = insertValueSearchByRecursive(arr, 0, arr.length - 1, 31);
		System.out.println(index);
	}

	/**
	 * 测试随机
	 * 可行
	 */
	@Test
	public void testRandomlyArray() {
		Random random = new Random();
		int[] nums = new int[100];
		for (int i = 0; i < nums.length; i++) {
			nums[i] = random.nextInt(100);
		}
		Arrays.sort(nums);
		System.out.println(Arrays.toString(nums));

		int index = insertValueSearchByRecursive(nums, 0, nums.length - 1, 131);
		System.out.println(index);
	}
}
